//https://leetcode.cn/problems/lru-cache/description/?envType=daily-question&envId=2023-09-24


class Node{
public:
    Node*prev;
    Node*next;
    int val;
    int key;
    Node(int key,int num):key(key),val(num){
    }
};
class DeList{
private:
    unordered_map<int,Node*>dictionary;
    int maxSize;
    int curSize;
    Node* head;
    Node* tail;
public: 
    DeList(int settingSize):maxSize(settingSize){
        curSize = 0;
        head = new Node(0,0);
        tail = new Node(0,0);
        head->next = tail;
        tail->prev = head;
    }
    void Insert(int key,int newValue){
        if(dictionary.count(key)){
            dictionary[key]->val = newValue;
            dictionary[key]->prev->next = dictionary[key]->next;
            dictionary[key]->next->prev = dictionary[key]->prev;
            InsertBack(key);
        }else{
            if(curSize==maxSize){
                Delete(head->next->key);
            }
            dictionary[key] = new Node(key,newValue);
            InsertBack(key);
            curSize++;
        }
    }
    void InsertBack(int key){
        dictionary[key]->prev = tail->prev;
        dictionary[key]->next = tail;
        tail->prev->next = dictionary[key];
        tail->prev = dictionary[key];  
    }
    void Delete(int key){
        dictionary[key]->prev->next = dictionary[key]->next;
        dictionary[key]->next->prev = dictionary[key]->prev;
        curSize--;
        dictionary.erase(key);
    }
    int get(int key){
        return dictionary.count(key)?dictionary[key]->val:-1;
    }
};
class LRUCache {//LRU-双锻链表-数据结构设计
public:
    DeList* deList;
    LRUCache(int capacity) {
        deList = new DeList(capacity);
    }
    
    int get(int key) {
        int temp = deList->get(key); 
        if(temp!=-1){deList->Insert(key,temp);}
        return temp;
    }
    
    void put(int key, int value) {   
        return deList->Insert(key,value);
    }
};